package string;

/**
 * 给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，
 * 它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
 * 请你返回 s 中好分割的数目。
 * <p>
 * 示例 1：
 * 输入：s = "aacaba"
 * 输出：2
 * 解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
 * ("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
 * ("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
 * ("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
 * ("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
 * ("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
 * <p>
 * 示例 2：
 * 输入：s = "abcd"
 * 输出：1
 * 解释：好分割为将字符串分割成 ("ab", "cd") 。
 * <p>
 * 示例 3：
 * 输入：s = "aaaaa"
 * 输出：4
 * 解释：所有分割都是好分割。
 * <p>
 * 示例 4：
 * 输入：s = "acbadbaada"
 * 输出：2
 *
 * @author Jisheng Huang
 * @version 20250519
 */
public class NumOfGoodWaysSplit_1525 {
    /**
     * 注意到当我们已经统计出字符串的前 i−1 个字符中的不同字符数量时，我们可以利用该信息算出字符串前 i 个字符的不同字符数量。记字符串的前
     * i 个字符（为了方便处理边界情况，下标从 1 开始编号）中的不同字符数量为 f[i]，当第 i 个字符在字符串前 i−1 个字符中出现过时，
     * f[i]=f[i−1]，否则 f[i]=f[i−1]+1。
     *
     * @param s the given string
     * @return the number of good ways to split the given string
     */
    public static int numSplits(String s) {
        int n = s.length();
        int[] left = new int[n + 2];
        int[] right = new int[n + 2];
        boolean[] recLeft = new boolean[26];
        boolean[] recRight = new boolean[26];

        for (int i = 1; i <= n; ++i) {
            int c = s.charAt(i - 1) - 'a';

            if (recLeft[c]) {
                left[i] = left[i - 1];
            } else {
                recLeft[c] = true;
                left[i] = left[i - 1] + 1;
            }
        }

        for (int i = n; i > 0; --i) {
            int c = s.charAt(i - 1) - 'a';

            if (recRight[c]) {
                right[i] = right[i + 1];
            } else {
                recRight[c] = true;
                right[i] = right[i + 1] + 1;
            }
        }

        int ret = 0;

        for (int i = 1; i < n; ++i) {
            if (left[i] == right[i + 1]) {
                ++ret;
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        String s = "aacaba";
        System.out.println(numSplits(s));

        s = "abcd";
        System.out.println(numSplits(s));

        s = "aaaaa";
        System.out.println(numSplits(s));

        s = "acbadbaada";
        System.out.println(numSplits(s));
    }
}
